Computer networks form the basis for IT (Information Technology) infrastructure in a wide variety of contexts. Such computer networks comprise interconnected devices of various types. The purpose of the network is to support the flow of messages between those devices so as to deliver information, applications and services, etc., over the network. A number of techniques are available for managing a network. In this context, managing a network includes monitoring the network to identify failure points and other problematic areas, such as hotspots, and providing information to administrators and users of the network to allow the problems to be fixed. There are a number of tools available for providing a network topology. The topology of a network identifies how devices in the network are physically or logically connected to each other. Thus, any particular single device may have one or more connections to a neighbour device. Computerised tools which “discover” a network are available, and they create network topologies which define the interconnection of the devices in the network, and the nature of those devices.
Determining network topology can be done in many ways. Techniques that can all be utilised separately or in combination to give a good representation of network connectivity include, for example:                Cisco Discovery Protocol (CDP)        Link Layer Discovery Protocol (LLDP)        SynOptics Network Management Protocol (SoNMP)        Spanning Tree Protocol (STP)        IP Traceroute        IPv6 Neighbour Discovery        user additions/modifications/deletions        
Knowing the topology of a network is extremely useful, but it does not provide a solution to all of the problems which can occur. Networks are increasingly used to provide the infrastructure for supporting the delivery of applications and services between remote geographical locations, either over long distances or in extremely complex networks with a large number of interconnected devices. Increasingly, network administrators and users are interested to know not necessarily the full details of the network, but to understand the performance of the delivery of applications and services over a network. Thus, so-called “end to end” monitoring is becoming increasingly popular. With “end to end” monitoring, applications involving message flow from a source device to a destination device have their performance monitored as they are delivered between that source and destination device. The performance parameters can be used to estimate or guess at possible failures in the network, although they do not provide any specific information about the location of those failures and therefore do not point directly to a solution.
Often a source device is a server providing a particular service, and the destination device is a client terminal which is connected to the server via the network and which requires to use that service. The term “device” used herein is intended to cover any devices which can be connected in a network. The term “server” is used to denote a device which is responsible for delivering a service or application, and the term “client” is used to denote a device (either user-based or another dependent machine or server) which depends on that application or service.
A significant difficulty in guessing where a problem might lie when it can be seen that an application's performance is deteriorating is a lack of understanding about the path through the network that message flow for that application might have taken. Networks depend on many types of network devices (e.g. routers, switches, firewalls, load balancers, etc.) to connect their endpoint devices, such that it is extremely difficult to say for any given source endpoint how the message from that endpoint will be routed through the network to a given destination endpoint. The complexity of such path determination is exacerbated by the usage of multiple alternating paths, redundant paths, load balancing, etc.
Attempts have been made to predict how a particular packet will be routed through a network. Such predictions are based on a complex model of the network topology together with indications on a per device basis as to how a particular device will behave in the network. Network devices can be highly sophisticated, and there have been developed a large number of complex algorithms to determine a routing strategy at any particular device. Moreover, that routing strategy can depend on traffic and other environmental considerations which affect the network (such as failure of other devices, etc.). Complex algorithms which can be applied by a device to determine a routing strategy can include for example:                Ingress interface and ingress interface technology        Packet headers (L2, L3, MPLS, ATM, etc)        Static and directly connected routes        Shared routing tables (full knowledge of BGP, OSPF, RIP, EIGRP, etc—active neighbours, link states, route costs, route weights, etc.)        Learned MAC forwarding tables        Access control lists        Network overlay technologies (e.g. MPLS, 802.1q VLANs), etc.        Loop avoidance technologies—e.g. PVSTP        Tunnelling protocols (MPLS, IPSEC, SSL, GRE)        Load balanced/redundant links        Default gateways        
However, even if it is in principle possible to predict where a given packet will be forwarded to next at a particular device, this requires a vast amount of data which is slow to gather, and can be out of date within seconds due to the real time nature of the operation of the routing devices. Furthermore, the mere acquisition of this data can place a significant load on both network devices and networks.
In addition, models required to simulate modern routing devices are extremely complex and, without the full model, their behaviour cannot be correctly predicted. To keep the model complete, it is necessary for such solutions to be regularly and rapidly updated to include developments in routing technologies.